package com.ch2;

import java.io.IOException;
import java.io.StringReader;
import java.util.Arrays;

/**
 * 左旋
 * @author Linxiaozhi
 *
 */
public class Rotate {
	/**
	 * 最大公约数
	 * @param i
	 * @param j
	 * @return
	 */
	static int gcd(int i, int j) {
		while (i != j) {
			if (i < j)
				j = j - i;
			else if (i > j)
				i = i - j;
		}
		return i;
	}

	static void move(int k, int[] arr) {
		System.out.println(Arrays.toString(arr));
		int size = arr.length;
		for (int i = k - 1; i >= 0; i--) {
			int temp = arr[i];
			int j = i;
			for (; j + k < size; j += k) {
				arr[j] = arr[j + k];
			}

			arr[j] = temp;
			System.out.println(Arrays.toString(arr));
		}

	}

//	static void rotate(int m, int[] arr) {
//		int size = arr.length;
//		int i = m, p = m;
//		int j = size - p;
//		while (i != j) {
//			if (i > j) {
//				swap(p - i, p, j, arr);
//				i -= j;
//			} else {
//				swap(p - i, p + j - i, i, arr);
//				j -= i;
//			}
//		}
//		swap(p - i, p, i, arr);
//
//	}

	static void rotate(int m, int[] arr) {
		rotate1(m, arr.length - m, m, arr);
	}

	static void rotate1(int i, int j, int m, int[] arr) {
		if (i == j) {
			swap(m - i, m, i, arr);
			return;
		}
		if (i > j) {
			swap(m - i, m, j, arr);
			rotate1(i - j, j, m, arr);
		} else {
			swap(m - i, m + j - i, m, arr);
			rotate1(i, j - i, m, arr);
		}
	}

	/**
	 * 交换a... a+m-1 和 b... b+m-1
	 * @param a
	 * @param b
	 * @param m
	 * @param arr
	 */
	private static void swap(int a, int b, int m, int[] arr) {
		for (int i = 0; i < m; i++) {
			int temp = arr[a + i];
			arr[a + i] = arr[b + i];
			arr[b + i] = temp;
		}
	}

	public static void main(String[] args) throws IOException {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		rotate(2, arr);
		System.out.println(Arrays.toString(arr));
	}
}
